package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

/**
 * Created with IntelliJ IDEA.
 * 2385. 感染二叉树需要的总时间
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/21 18:27
 */
public class AmountOfTime {

    private long max = 0;

    public int amountOfTime(TreeNode root, int start) {
        find(root, start);
        return (int) max - 1;
    }

    private long find(TreeNode node, int start) {
        if (node == null) {
            return 0;
        }
        long left = find(node.left, start);
        long right = find(node.right, start);
        if ((left >> 32) == 0 && (right >> 32) == 0) {
            if (start == node.val) {
                max = Math.max(max, Math.max(left, right) + 1);
                return 1L << 32;
            } else {
                return Math.max(left, right) + 1;
            }
        }
        if ((left >> 32) == 0) {
            max = Math.max(max, left + (right >> 32) + 1);
            return right + (1L << 32);
        }
        max = Math.max(max, right + (left >> 32) + 1);
        return left + (1L << 32);
    }

}
